package ch09_04;

import java.util.*;

public class Solution {
    public static List<List<Integer>> subsets(int N) {
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	for (int i = 0; i < N; i++) {
	    map.put(1 << i, i);
	}
	List<List<Integer>> allSets = new ArrayList<List<Integer>>();
	for (int i = 0; i < (1 << N); i++) {
	    List<Integer> list = new ArrayList<Integer>();
	    int j = i;
	    while (j != 0) {
		int position = j & (-j);
		list.add(map.get(position));
		j &= (j - 1);
	    }
	    allSets.add(list);
	}
	return allSets;
    }

    public static void main(String... args) {
	int N = 20;
	List<List<Integer>> allSets = subsets(N);
	for (List<Integer> list : allSets) {
	    System.out.println(list.toString());
	}
    }
}